﻿using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;
using System.Diagnostics;

namespace TreeTraversal
{
    public partial class Form1 : Form
    {
        int m_RandIndex = 0;
        int m_LastRandValue = 0;
        int m_NextRandValue = 0;
        int m_RandSeed = 0;
        int m_RandMin = 0;
        int m_RandMax = 50;
        Random m_Rand;
        BinaryTree<double> m_BinaryTree;

        int GetRandom()
        {

            try
            {
                int next = m_Rand.Next(m_RandMin, m_RandMax);
                return next;
            }
            catch
            {

                return 0;
            }
        }

        public Form1()
        {
            InitializeComponent();
            this.DoubleBuffered = true;

            //Form2 testForm = new Form2();
            //testForm.Show();

            splitContainer1.SplitterWidth = 10;
            borderlessTextBox1.TextBox.KeyDown += textBox1_KeyDown;

            m_Rand = new Random(m_RandSeed);
            textBoxRandomSeed.Tag = label4;
            textBoxRandomSeed.TextBox.Text = m_RandSeed.ToString();
            textBoxRandomSeed.MouseEnter += borderlessTextBox_MouseEnter;
            textBoxRandomSeed.MouseLeave += borderlessTextBox_MouseLeave;

            textBoxRandomMin.Tag = label2;
            textBoxRandomMin.TextBox.Text = m_RandMin.ToString();
            textBoxRandomMin.MouseEnter += borderlessTextBox_MouseEnter;
            textBoxRandomMin.MouseLeave += borderlessTextBox_MouseLeave;

            textBoxRandomMax.Tag = label3;
            textBoxRandomMax.TextBox.Text = m_RandMax.ToString();
            textBoxRandomMax.MouseEnter += borderlessTextBox_MouseEnter;
            textBoxRandomMax.MouseLeave += borderlessTextBox_MouseLeave;

            m_NextRandValue = GetRandom();

            label1.Text = "Balanced Binary Search Tree";
            m_BinaryTree = new BalancedBinarySearchTree<double>();
            for (int i = 0; i < 0; i++)
            {
                m_BinaryTree.Add(GetNextRand());
            }

            //int[] intArray = new int[15];
            //for (int i = 0; i < intArray.Length; i++)
            //{
            //    intArray[i] = i;
            //}

            //BinarySearchTree<int> binaryTree2 = new BinarySearchTree<int>();
            //PopulateTreeFromArray(intArray, 0, intArray.Length, binaryTree2);

            //m_BinaryTree = CreateFullBinaryTree(5);
            //this.Text = binaryTree.Count.ToString();

            //BinaryTreeNode<uint> tmpNode = binaryTree.Find(0);
            //while (tmpNode != null)
            //{
            //    VisitNode(tmpNode);
            //    tmpNode = GetNextInOrderNode(tmpNode);
            //}

            VisitAllNodes();
            
            //InOrderTraversal(binaryTree.Root);
            //listBox1.Items.Add("");
            //PreOrderTraversal(binaryTree.Root);
            //listBox1.Items.Add("");
            //PostOrderTraversal(binaryTree.Root);
        }

        void ReplaceTreeImage(Image NewImage)
        {
            pictureBox1.SuspendLayout();

            Image oldImage = null;
            Size oldSize = new Size();
            if (pictureBox1.Image != null)
            {
                oldImage = pictureBox1.Image;
                oldSize = oldImage.Size;
            }

            //panel1.SuspendLayout();
            pictureBox1.Image = NewImage;
            if (NewImage != null)
            {
                pictureBox1.Size = NewImage.Size;
                int scrollBarSize = panel1.HorizontalScroll.LargeChange;
                if (oldSize != NewImage.Size)
                {
                    panel1.AutoScrollPosition = new Point((pictureBox1.Width / 2) - (panel1.Width / 2), 0);
                    //panel1.HorizontalScroll.Value = (panel1.HorizontalScroll.Maximum / 2) - (scrollBarSize / 2);
                }

                //int deltaWidth = NewImage.Size.Width - oldSize.Width;
                //double temp = deltaWidth / 2;
                //double temp2 = temp / NewImage.Size.Width;

                //int scrollBarSize = panel1.HorizontalScroll.LargeChange;

                //
                ////panel1.HorizontalScroll.
                //int tempPos = panel1.HorizontalScroll.Value + (int)(panel1.HorizontalScroll.Maximum * temp2);
                //if (tempPos >= 0 && tempPos < panel1.HorizontalScroll.Maximum)
                //{
                //    panel1.HorizontalScroll.Value = tempPos;
                //}
            }
            else
            {
                pictureBox1.Size = new Size();
            }
            
            if (oldImage != null)
            {
                oldImage.Dispose();
            }

            pictureBox1.ResumeLayout();
        }

        //const int m_NodeSize = 35;
        int m_VerticalOffset;
        void DrawTree<T>(BinaryTreeNode<T> RootNode)
        {
            if (RootNode == null)
            {
                ReplaceTreeImage(null);
                return;
            }

            Size nodeImageSize = RootNode.NodeImageSize;
            m_VerticalOffset = nodeImageSize.Height * 2;

            int height = RootNode.MaxDepth;
            int maxHorizontolNodes = (int)Math.Pow(2, height);

            int bitmapWidth = (int)(nodeImageSize.Width * 1.5 * maxHorizontolNodes);
            int bitmapHeight = 15 + m_VerticalOffset * (height + 1);

            Bitmap bitmap = new Bitmap(bitmapWidth, bitmapHeight);
            using (Graphics graphics = Graphics.FromImage(bitmap))
            {
                graphics.SmoothingMode = System.Drawing.Drawing2D.SmoothingMode.AntiAlias;
                DrawTree(RootNode, graphics, new Rectangle(0, 15, bitmap.Width, nodeImageSize.Height));
            }

            ReplaceTreeImage(bitmap);
        }

        Point GetCenterPoint(Rectangle rect)
        {
            return new Point(rect.X + (int)(rect.Width / 2), rect.Y + (rect.Height / 2));
        }

        void DrawTree<T>(BinaryTreeNode<T> RootNode, Graphics graphics, Rectangle rect)
        {
            if (RootNode == null)
                return;

            Size nodeImageSize = RootNode.NodeImageSize;

            Point Center = GetCenterPoint(rect);
            int x = Center.X - (nodeImageSize.Width / 2);

            Rectangle leftRect = new Rectangle(rect.X, rect.Y + m_VerticalOffset, rect.Width / 2, rect.Height);
            Rectangle rightRect = new Rectangle(rect.X + rect.Width / 2, rect.Y + m_VerticalOffset, rect.Width / 2, rect.Height);
            if (RootNode.Left != null)
            {
                Point centerPoint = GetCenterPoint(leftRect);
                graphics.DrawLine(Pens.Black, Center, centerPoint);
            }

            if (RootNode.Right != null)
            {
                Point centerPoint = GetCenterPoint(rightRect);
                graphics.DrawLine(Pens.Black, Center, centerPoint);
            }

            using (Bitmap nodeImage = RootNode.GetNodeImage())
            {
                graphics.DrawImage(nodeImage, x, rect.Y);
            }

            //graphics.FillEllipse(Brushes.Red, new Rectangle(x, rect.Y, m_NodeSize - 1, m_NodeSize - 1));

            //Font font = SystemFonts.DefaultFont;
            //string value = RootNode.Value.ToString();
            //SizeF stringSize = graphics.MeasureString(value, font);
            //graphics.DrawString(value, font, Brushes.Maroon, Center.X - (stringSize.Width / 2), Center.Y - (stringSize.Height / 2));

            DrawTree(RootNode.Left, graphics, leftRect);
            DrawTree(RootNode.Right, graphics, rightRect);
        }

        void VisitAllNodes()
        {
            DrawTree(m_BinaryTree.Root());
            //BalanceValues values = GetBalanceValues(m_BinaryTree.Root);

            listBox1.Items.Clear();
            int numNodesVisited = BreadthFirstTraversal(m_BinaryTree.Root());
            toolStripStatusLabel1.Text = 
                "Added: " + m_BinaryTree.Count +
                ", Visited: " + numNodesVisited.ToString() +
                ", RandIndex: " + m_RandIndex +
                ", LastRandValue: " + m_LastRandValue +
                ", NextRandValue: " + m_NextRandValue;
        }

        BinarySearchTree<uint> CreateFullBinaryTree(uint height)
        {
            uint numNodes = (uint)Math.Pow(2, height + 1) - 1;
            uint[] intArray = new uint[numNodes];
            for (uint i = 0; i < intArray.Length; i++)
            {
                intArray[i] = i;
            }

            BinarySearchTree<uint> binaryTree = new BinarySearchTree<uint>();
            PopulateTreeFromArray(intArray, 0, intArray.Length, binaryTree);

            return binaryTree;
        }

        void PopulateTreeFromArray(uint[] intArray, int startIndex, int length, BinarySearchTree<uint> tree)
        {
            if (length == 0)
                return;

            int middleIndex = startIndex + (length / 2);
            tree.Add(intArray[middleIndex]);
            PopulateTreeFromArray(intArray, startIndex, middleIndex - startIndex, tree);
            PopulateTreeFromArray(intArray, middleIndex + 1, middleIndex - startIndex, tree);
        }

        BinaryTreeNode<T> GetNextInOrderNode<T>(BinaryTreeNode<T> rootNode) where T : IComparable
        {
            if (rootNode == null)
                return null;

            // find leftmost leaf in right sub tree
            // if null, return parent if node is parent's left node
            // otherwise travel up the tree until a node with (node.parent.left == node) is found
            // return null if node is rightmost leaf of tree.

            BinaryTreeNode<T> leftMostInRightSubTree = null;
            if (rootNode.Right != null)
            {
                leftMostInRightSubTree = rootNode.Right;
                while (leftMostInRightSubTree.Left != null)
                {
                    leftMostInRightSubTree = leftMostInRightSubTree.Left;
                }
            }

            if (leftMostInRightSubTree != null)
            {
                return leftMostInRightSubTree;
            }
            else
            {
                while (rootNode.Parent != null)
                {
                    if (rootNode.Parent.Left == rootNode)
                        return rootNode.Parent;
                    else
                    {
                        rootNode = rootNode.Parent;
                    }
                }

                return rootNode.Parent;
            }

            return null;
        }

        int BreadthFirstTraversal<T>(BinaryTreeNode<T> rootNode)
        {
            int numNodesVisited = 0;
            if (rootNode == null)
                return numNodesVisited;

            HashSet<T> hashSet = new HashSet<T>();
            Queue<BinaryTreeNode<T>> queue = new Queue<BinaryTreeNode<T>>();
            queue.Enqueue(rootNode);
            int rowNodeCount = 1;

            int treeHeight = -1;
            int nextRowNodeCount = 0;
            int step = 0;
            while (queue.Count > 0)
            {
                BinaryTreeNode<T> node = queue.Dequeue();
                numNodesVisited++;
                //Debug.Assert(!hashSet.Contains(node.Value));
                hashSet.Add(node.Value);
                VisitNode(node);
                if (node.Left != null)
                {
                    nextRowNodeCount++;
                    queue.Enqueue(node.Left);
                }
                if (node.Right != null)
                {
                    nextRowNodeCount++;
                    queue.Enqueue(node.Right);
                }

                step++;
                if (step == rowNodeCount && queue.Count > 0)
                {
                    treeHeight++;
                    // start new row...
                    listBox1.Items.Add("--------------------------------------------");
                    step = 0;
                    rowNodeCount = nextRowNodeCount;
                    nextRowNodeCount = 0;
                }
            }

            return numNodesVisited;
        }

        class BalanceValues
        {
            public int LeftDepth = 0;
            public int RightDepth = 0;
            public int MaxDepth { get { return Math.Max(LeftDepth, RightDepth); } }
            public int Balance { get { return RightDepth - LeftDepth; } }
        }

        BalanceValues GetBalanceValues<T>(BinaryTreeNode<T> Node) where T : IComparable
        {
            BalanceValues values = new BalanceValues();

            if (Node.Left != null)
            {
                Debug.Assert(Node.Value.CompareTo(Node.Left.Value) > 0);
                BalanceValues leftValues = GetBalanceValues(Node.Left);
                values.LeftDepth = leftValues.MaxDepth + 1;
            }

            if (Node.Right != null)
            {
                Debug.Assert(Node.Value.CompareTo(Node.Right.Value) < 0);
                BalanceValues rightValues = GetBalanceValues(Node.Right);
                values.RightDepth = rightValues.MaxDepth + 1;
            }

            Debug.Assert(Node.Balance == values.Balance);
            Debug.Assert(Math.Abs(values.Balance) < 2);

            return values;
        }

        void InOrderTraversal<T>(BinaryTreeNode<T> rootNode)
        {
            if (rootNode == null)
                return;

            InOrderTraversal(rootNode.Left);
            VisitNode(rootNode);
            InOrderTraversal(rootNode.Right);
        }

        void PreOrderTraversal<T>(BinaryTreeNode<T> rootNode)
        {
            if (rootNode == null)
                return;

            VisitNode(rootNode);
            PreOrderTraversal(rootNode.Left);
            PreOrderTraversal(rootNode.Right);
        }

        void PostOrderTraversal<T>(BinaryTreeNode<T> rootNode)
        {
            if (rootNode == null)
                return;

            PostOrderTraversal(rootNode.Left);
            PostOrderTraversal(rootNode.Right);
            VisitNode(rootNode);
        }        

        void VisitNode<T>(BinaryTreeNode<T> node)
        {
            string tempValues = "";
            if (node.Parent != null)
                tempValues += "P: " + node.Parent.Value;
            if (node.Left != null)
                tempValues += " L: " + node.Left.Value;
            if (node.Right != null)
                tempValues += " R: " + node.Right.Value;

            string temp = node.Value + "\t(LD: " + node.LeftDepth + ", RD: " + node.RightDepth + ", B: " + node.Balance + ")\t   " + tempValues;
            int index = listBox1.Items.Add(temp);

            if (Math.Abs(node.Balance) > 1)
            { 
                //listBox1.for
            }
        }

        int GetNextRand()
        {
            m_LastRandValue = m_NextRandValue;
            m_NextRandValue = GetRandom();
            m_RandIndex++;
            return m_LastRandValue;
        }

        private void button1_Click(object sender, EventArgs e)
        {
            try
            {
                int tempSeed = Convert.ToInt32(textBoxRandomSeed.TextBox.Text);
                if (tempSeed != m_RandSeed)
                {
                    m_Rand = new Random(tempSeed);
                    m_RandSeed = tempSeed;
                }

                m_RandMin = Convert.ToInt32(textBoxRandomMin.TextBox.Text);
                m_RandMax = Convert.ToInt32(textBoxRandomMax.TextBox.Text);

                AddValueToTree(GetNextRand());
            }
            catch
            {
                Debug.Assert(false);
            }
        }

        void AddValueToTree(double Value)
        {
            m_BinaryTree.Add(Value);
            toolStripStatusLabel2.Text = "Added " + Value;
            VisitAllNodes();
        }

        private void button2_Click(object sender, EventArgs e)
        {
            AddCustomValue();
        }

        void AddCustomValue()
        {
            try
            {
                borderlessTextBox1.TextBox.SelectAll();

                double value = Convert.ToDouble(borderlessTextBox1.TextBox.Text);
                AddValueToTree(value);
            }
            catch
            {
            }
        }

        private void textBox1_KeyDown(object sender, KeyEventArgs e)
        {
            if (e.KeyCode == Keys.Enter)
            { 
                AddCustomValue();
                e.Handled = true;
                e.SuppressKeyPress = true;
            }
        }

        private void Form1_Shown(object sender, EventArgs e)
        {
            borderlessTextBox1.TextBox.Focus();
        }

        void OnCreateNewTree()
        {
            toolStripStatusLabel2.Text = string.Empty;
            label1.Text = m_BinaryTree.Name;
            VisitAllNodes();
        }

        private void newBalancedBinarySearchTreeToolStripMenuItem_Click(object sender, EventArgs e)
        {
            m_BinaryTree = new BalancedBinarySearchTree<double>();
            OnCreateNewTree();
        }

        private void newBinarySearchTreeToolStripMenuItem_Click(object sender, EventArgs e)
        {
            m_BinaryTree = new BinarySearchTree<double>();
            OnCreateNewTree();
        }

        private void newHeapToolStripMenuItem_Click(object sender, EventArgs e)
        {
            m_BinaryTree = new Heap<double>();
            OnCreateNewTree();
        }

        private void newMaxHeapToolStripMenuItem_Click(object sender, EventArgs e)
        {
            m_BinaryTree = new DirectionalHeap<double>(DirectionalHeapType.Max);
            OnCreateNewTree();
        }

        private void newMinHeapToolStripMenuItem_Click(object sender, EventArgs e)
        {
            m_BinaryTree = new DirectionalHeap<double>(DirectionalHeapType.Min);
            OnCreateNewTree();
        }

        private void saveTreeImageToolStripMenuItem_Click(object sender, EventArgs e)
        {
            if (saveFileDialog1.ShowDialog() == System.Windows.Forms.DialogResult.OK)
            {
                pictureBox1.Image.Save(saveFileDialog1.FileName, System.Drawing.Imaging.ImageFormat.Png);
            }
        }

        private void button3_Click(object sender, EventArgs e)
        {
            if (myPanel1.Visible == false)
                myPanel1.Visible = true;
            else
                myPanel1.Visible = false;
        }

        private void borderlessTextBox_MouseEnter(object sender, EventArgs e)
        {
            if (sender is BorderlessTextBox)
            {
                BorderlessTextBox borderlessTextBox = sender as BorderlessTextBox;
                object tag = borderlessTextBox.Tag;
                if (tag is Label)
                {
                    Label label = tag as Label;
                    label.BackColor = Color.FromArgb(0x55, Color.Turquoise);
                }
            }
        }

        private void borderlessTextBox_MouseLeave(object sender, EventArgs e)
        {
            if (sender is BorderlessTextBox)
            {
                BorderlessTextBox borderlessTextBox = sender as BorderlessTextBox;
                object tag = borderlessTextBox.Tag;
                if (tag is Label)
                {
                    Label label = tag as Label;
                    label.BackColor = System.Drawing.SystemColors.Control;
                }
            }
        }

        private void exitToolStripMenuItem_Click(object sender, EventArgs e)
        {
            this.Close();
        }
    }   
}
